package com.devshephard.rpcframework.acm.tree.util;

public class DP {
    public static void main(String[] args) {


        int i = 0;
        int[] nums = new int[]{4,1,1,9,1};
        //DP_METHOD(nums,0,4);
        DP dp = new DP();
        System.out.println(dp.rob(nums));


    }

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[nums.length - 1];
    }


    public static int DP_METHOD(int[] nums,int i,int max){


        if(nums.length == 1){
            return nums[0];
        }

        //如果有两个,则选最大
        if(nums.length == 2){
            if(nums[0] > nums[1]){
                return nums[0];
            }else {
                return nums[1];
            }
        }

        if(i + 2 >= nums.length){
            System.out.println(max);
            return 1;
        }

        int a = max + nums[i + 2];
        int b = nums[i + 1];

        max = Math.max(a,b);

        //如果有三个,由于不能走相邻的数字,则选一个最大
        //MAX(nums[i],nums[i+1])+nums[i+2]


        i = i+2;

        if (i  == nums.length - 1){
            System.out.println(max);
        }else {
            return DP_METHOD(nums,i,max);
        }


        //DP_METHOD(nums);


       return 1;

    }


}
